package com.demo.java.OD301_350.OD327;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【求符合条件元组个数(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146119229
 */
public class OdMain {
    private static int res = 0;  // 结果计数
    private static int target;  // 目标值
    private static Set<List<Integer>> numsSet = new HashSet<>();  // 存储已计算的组合，避免重复

    public static void main(String[] args) {
        // 创建Scanner对象来读取输入
        Scanner sc = new Scanner(System.in);

        // 读取数组
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 读取k和目标值target
        int k = sc.nextInt();
        target = sc.nextInt();

        // 排序nums，方便剪枝和去重
        Arrays.sort(nums);

        // 调用递归方法进行组合计算
        combine(nums, k, new ArrayList<>(), 0, 0);

        // 输出结果
        System.out.println(res);
    }

    // 递归组合函数
    public static void combine(int[] nums, int n, List<Integer> list, int index, int sum) {
        // 如果选择了k个数字
        if (n == 0) {
            // 如果和等于目标值
            if (sum == target) {
                numsSet.add(new ArrayList<>(list));  // 使用Set避免重复组合
                res++;  // 结果计数加1
            }
        } else {
            for (int i = index; i < nums.length; i++) {
                // 去重，跳过相同的数字
                if (i > index && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 如果当前和已经大于目标值，剪枝
                if (sum + nums[i] > target) {
                    break;
                }
                // 添加当前数字到组合中
                list.add(nums[i]);
                // 递归选择下一个数字
                combine(nums, n - 1, list, i + 1, sum + nums[i]);
                // 回溯，移除当前数字
                list.remove(list.size() - 1);
            }
        }
    }
}